#include <iostream>
#include <queue>
using namespace std;
const int N=1e3+10;

int dp[N][N];
char a[N][N];
int n,k;
int ret;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
struct node{
	int x,y,wd;
};
int bfs()
{
	queue<node> q;
	q.push({1,1,0});
	a[1][1]='X';
	int step=0;
	while(q.size())
	{
		int sz=q.size();
		step++;
		while(sz--)
		{
			node u=q.front();
			q.pop();
			for(int i=0;i<4;i++)
			{
				int nx=u.x+dx[i];
				int ny=u.y+dy[i];
				int wd=0;
				if(nx<1 || nx>n || ny<1 || ny>n || a[nx][ny]=='#')
					continue;
				if(nx==n && ny==n)
					return step;
				if(a[nx][ny]=='X')
				{
					if(u.wd==0)
						continue;
					else if(u.wd>0)
					{
						q.push({nx,ny,u.wd-1});
					}
				}
				else if(a[nx][ny]=='%')
				{
					q.push({nx,ny,k});
					a[nx][ny]='X';
				}
				else{
					if(u.wd>0)
						q.push({nx,ny,u.wd-1});
					else
						q.push({nx,ny});
					a[nx][ny]='X';
				}
			}		
				
		}
	}
	return -1;
}
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		getchar();
		for(int j=1;j<=n;j++)
		{
			cin>>a[i][j];
		}
	}
	ret=bfs();
	cout<<ret<<endl;
	return 0;
}
